package 剑指Offer1;

public class _33二叉搜索树与双向链表 {
    class Node {
        public int val;
        public Node left;
        public Node right;

        public Node() {}

        public Node(int _val) {
            val = _val;
        }

        public Node(int _val,Node _left,Node _right) {
            val = _val;
            left = _left;
            right = _right;
        }
    }

    private Node pre,head;
    public Node treeToDoublyList(Node root) {
        if(root == null) return null;
        inorder(root);
        head.left = pre;
        pre.right = head;
        return head;
    }

    private void inorder(Node cur){
        if(cur == null) return;
        inorder(cur.left);
        if(pre!=null){ //pre指向上一个节点，当pre为null,此时cur指向头节点
            //链接上一个节点指向当前节点
            pre.right = cur;
        }else{
            head = cur; //pre为null,此时该递归里cur指向当前节点
        }
        cur.left = pre; //链接当前节点和上一个节点
        pre = cur; //更新pre指向下一个节点，在下次递归里指向上一个节点
        inorder(cur.right);

        //递归完毕,pre指向最后一个节点,head指向头节点
    }
}
